package com.mdnote.practice.binary_search;

import java.util.Map;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/18
 * @description  x 的平方根
 */
public class LeetCode69 {

    public static void main(String[] args) {
        LeetCode69 leetCode69 = new LeetCode69();
        int i = leetCode69.mySqrt(8);
        System.out.println(i);
    }

    public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        // binary search
//        int res = binarySearch(x);
        // for loop
        int res = forLoop(x);
        return res;
    }

    private int forLoop(int x) {

        double xn = x, C = x;
        while (true) {
            double xn1 = 0.5 * (xn + C /xn);
            if (Math.abs(xn1 - xn) < 1e-7) {
                break;
            }
            xn = xn1;
        }
        return (int) xn;
    }

    private int binarySearch(int x) {

        int left = 0;
        int right = x;

        int res = 0;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (mid * mid == x) {
                return mid;
            }
            if (mid * mid < x) {
                res = mid;
                left = mid + 1;
            }
            if (mid * mid > x) {
                right = mid - 1;
            }
        }
        return res;
    }
}
